package com.ds.bintree.LeetCode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author Dianzhi Han
 * @version 1.0
 * @description: TODO
 * @date 2022/9/14 18:12
 */
public class Num106_InAndPostBuildTree2 {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        TreeNode root = new TreeNode(postorder[postorder.length-1]);
        Deque<TreeNode> stack = new LinkedList<>();
        int index = inorder.length-1; // 中序遍历数组从后往前
        stack.push(root); // 根节点先入栈
        for (int i = postorder.length-2; i >=0; i--) {
            TreeNode peek = stack.peek();
            /**
             * 如果和栈顶不一样则就是栈顶右子树，否则就是栈里面某个祖先的左子树
             */
            if (peek.val!=inorder[index]){
                TreeNode cur = new TreeNode(postorder[i]);
                peek.right = cur;
                stack.push(cur);
            }else{
                while (!stack.isEmpty() && stack.peek().val == inorder[index]){
                    peek = stack.pop();
                    index--;
                }
                TreeNode cur = new TreeNode(postorder[i]);
                peek.left = cur;
                stack.push(cur);
            }
        }
        return root;
    }
}